package com.ys.p5Stack栈;

/**
 * 描述:
 * 使用链表模拟实现 Stack 栈
 * 核心: 入口与出口都是栈顶
 * 链表实现的数据结构一般没有 限制结构,当然也可以做有限资源
 *
 * @author CodeYang
 * @version 2021/1/4 1:15
 */
public class LinkedStack<E> implements Stack<E> {

    /**
     * 栈顶
     */
    private LinkedStackNode<E> topNode;

    /**
     * 栈的实际元素
     */
    private int size;

    public LinkedStack() {
        topNode = null;
    }


    /**
     * 入栈操作
     *
     * @param element
     */
    @Override
    public boolean push(E element) {
        // 栈空
        if (isEmpty()) {
            // 栈空 就把当前节点作为栈顶
            topNode = new LinkedStackNode<>(element);
        } else {
            // 栈不空--> 初始化栈c -- > 更新元素到栈顶
            LinkedStackNode<E> node = new LinkedStackNode<>(element);
            // 把节点添加到栈顶之前
            node.next = topNode;
            //更新栈顶
            topNode = node;
        }
        size++;

        return true;
    }

    /**
     * 出栈操作
     *
     * @return
     */
    @Override
    public E pop() {
        // 先进后出 操作栈顶 --> 先弹栈顶 更新栈顶到下一个节点
        // 1栈空
        if (isEmpty()){
            return null;
        }
        // 2 栈不空
        E oldValue = topNode.item;
        // 获得栈顶元素的下一个节点(和之后的关系)
        LinkedStackNode<E> nextNode = topNode.next;
        // GC回收
        topNode.next = null;
        // 更新栈顶
        topNode = nextNode;
        size--;
        return oldValue;
    }

    /**
     * 查看栈顶元素
     *
     * @return
     */
    @Override
    public E peek() {
        return isEmpty() ? null : topNode.item;
    }

    /**
     * 判断栈是否为空
     *
     * @return 如果栈为空，则返回true；如果栈为非空，则返回false。
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private static class LinkedStackNode<E> {
        /**
         * 数据
         */
        private E item;

        /**
         * 指针
         */
        private LinkedStackNode<E> next;

        /**
         * 初始化节点
         *
         * @param item
         */
        public LinkedStackNode(E item) {
            this.item = item;
        }
    }
}
